home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 4 / Info_Mac IV CD-ROM (Pacific HiTech Inc.)(August 1994).iso / Development / Source / StusThreadUtils Folder / ThreadSynch.h < prev   
Encoding:
Text File  |  1994-03-19  |  7.4 KB  |  174 lines  |  [TEXT/KAHL]
  1. // ThreadSynch.h
  2. // 
  3. // (C) 6th March 1994  Stuart Cheshire <cheshire@cs.stanford.edu>
  4. // 
  5. // This header file defines three synchronization primitives:
  6. // Semaphores, Mutual exclusion locks, and Condition variables.
  7. // They can all be allocated in static storage, dynamic storage,
  8. // or on the stack, and should be initialized (by calling xxxInit)
  9. // before use. (In C++, a constructor would do this automatically.)
  10. //
  11. // If you aren't familiar with Semaphores, Mutual exclusion locks,
  12. // and Condition variables, pick up a good Operating Systems text book.
  13. //
  14. //
  15. // Brief explanation (for those who were sleeping in lectures :-)
  16. //
  17. // Mutual exclusion locks are used to prevent two threads accessing the
  18. // same critical piece of code or the same critical piece of data at
  19. // the same time. Put MutexLockAcquire at the start of the critical
  20. // section and MutexLockRelease at the end. If a thread tries to do
  21. // a MutexLockAcquire while another thread is in the critical section,
  22. // it will wait until the other thread has finished before it proceeds.
  23. // It is an error to call MutexLockRelease if you do not hold the lock,
  24. // and it is an error to try to wait for a lock which you are already
  25. // holding yourself ("you" means a particular thread). These errors
  26. // are detected and reported via MacsBug breakpoints.
  27. //
  28. // Condition variables are used when you are waiting for a particular
  29. // condition to become true. The "country bridge" example in test.c
  30. // illustrates this. The easiest way to think of condition variables
  31. // is to consider the following evolution of a program:
  32. //
  33. //        while (!done)
  34. //            {
  35. //            MutexLockAcquire(&lock);
  36. //            if (A && B || C && D && E ...) { do_stuff(); done = TRUE; }
  37. //            MutexLockRelease(&lock);
  38. //            }
  39. //
  40. // The program keeps re-testing its condition until it is satisfactory,
  41. // and this does its stuff.
  42. // This could be re-written as follows to eliminate the variable "done":
  43. //
  44. //        MutexLockAcquire(&lock);
  45. //        while (!(A && B || C && D && E ...))
  46. //            { MutexLockRelease(&lock); Pause(); MutexLockAcquire(&lock); }
  47. //        do_stuff();
  48. //        MutexLockRelease(&lock);
  49. //
  50. // Now, while the condition is NOT satisfactory, the program releases
  51. // the lock, pauses for a moment, and then reclaims the lock to re-test
  52. // the condition. The question is, how long should the pause be? If it
  53. // is very short, then the while loop may execute millions of times,
  54. // wasting CPU time and slowing down everything else on the computer,
  55. // including the thing that the while loop is waiting for. If the pause
  56. // is too long, when the condition becomes true, the thread may be in
  57. // the middle of a long pause and it may be a long time before it wakes
  58. // up and "notices" that its condition is OK now. This is where condition
  59. // variables come to the rescue:
  60. //
  61. //        MutexLockAcquire(&lock);
  62. //        while (!(A && B || C && D && E ...)) ConditionVarWait(&cond);
  63. //        do_stuff();
  64. //        MutexLockRelease(&lock);
  65. //
  66. // Now, every time the program does anything that could change the truth
  67. // of the condition (ie changing the value of A, B, C, D or E ...) it is
  68. // required to signal this fact to the condition variable. What the
  69. // ConditionVarWait call does is to release the lock and put the thread
  70. // to sleep, waiting for this signal to arrive. When it arrives, the
  71. // thread wakes up and retests the condition. The ConditionVarWait routine
  72. // reaquires the lock before it returns to the caller, so the single call
  73. // to ConditionVarWait replaces the entire { Release; Pause; Acquire; }
  74. // sequence of the previous example.
  75. //
  76. // The ConditionVarSignal routine wakes up a single waiter, and the
  77. // ConditionVarBroadcast routine wakes up all of them. If you know that
  78. // the change you have made to the condition is such that ANY thread will
  79. // be able to make use of it and proceed, then it is okay to just wake up
  80. // one. If the change to the condition is such that some of the waiting
  81. // threads may be able to make use of it and some may not (as in the
  82. // "country bridge" example) then you MUST use ConditionVarBroadcast
  83. // so that they all get a chance to take a look at the new values.
  84. //
  85. // Before you can call ConditionVarWait, Signal or Broadcast, you must
  86. // be holding the lock that was associated with the Condition variable
  87. // when it was created (with ConditionVarInit). There are sound reasons
  88. // for this even though they may not always be obvious every time
  89. // (if you have variables that are changed in one thread and tested in
  90. // another, then all accesses to those variables should be protected by
  91. // a mutual exclusion lock). You may be tempted to cut corners with your
  92. // locking in some cases, but it's not worth it. Multi-threaded code is
  93. // hard enough to get right anyway, without inviting extra intermittent
  94. // unrepeatable bugs which are almost impossible to find.
  95. //
  96. //
  97. // Semaphores are simple basic counting primitives. It is easiest to think of
  98. // them counting some kind of abstract 'resource' which is in limited supply.
  99. //
  100. // Semaphores are not usually used directly -- they are the basis for
  101. // Mutual exclusion locks and Condition variables described above.
  102. //
  103. // If a buffer has n spaces in it, you can initialize a semaphore to n
  104. // to count the spaces. Each time you want to use a space in the buffer,
  105. // call P(semaphore) and it will decrement the count. If the count is
  106. // already zero, your thread will be stopped until the count increases
  107. // above zero again. When you have finished with your space in the buffer,
  108. // call V(semaphore) to increment the count and indicate that the resource
  109. // is now available for someone else again. If there is another thread
  110. // currently waiting in a P call, it will be woken up so that it can use
  111. // the space which has become available.
  112. //
  113. // If you have a critical section of code, then a semaphore initialized
  114. // to one can act as a mutual exclusion lock (because ONE thread is allowed
  115. // to execute the code at a time).
  116. //
  117. // If you wish to signal from one thread to another, a semaphore initialized
  118. // zero can achieve this (there is initially NO signal, until the signalling
  119. // thread calls V(semaphore) to cause the signal to come into existence).
  120.  
  121. #ifndef __THREADSYNCH__
  122. #define __THREADSYNCH__
  123.  
  124. #include    <Threads.h>
  125.  
  126. // *****************************************************************
  127. // Semaphore. Operations: Init, Proben (test), Verhogen (increment)
  128.  
  129. typedef struct SemaphoreWaiter SemaphoreWaiter;
  130. typedef struct
  131.     {
  132.     long value;
  133.     SemaphoreWaiter *head;
  134.     SemaphoreWaiter **tail;
  135.     } Semaphore;
  136.  
  137. extern void SemaphoreInit(Semaphore *s, long initialvalue);
  138. extern void SemaphoreP(Semaphore *s);
  139. extern void SemaphoreV(Semaphore *s);
  140.  
  141. #define SemaphoreAcquire SemaphoreP
  142. #define SemaphoreRelease SemaphoreV
  143.  
  144. // *****************************************************************
  145. // MutexLock. Operations: Init, Acquire, Release
  146.  
  147. typedef struct
  148.     {
  149.     Semaphore sem;
  150.     ThreadID lockholder;
  151.     } MutexLock;
  152.  
  153. extern void MutexLockInit(MutexLock *m);
  154. extern void MutexLockAcquire(MutexLock *m);
  155. extern void MutexLockRelease(MutexLock *m);
  156.  
  157. // *****************************************************************
  158. // ConditionVar. Operations: Init, Wait, Signal, Broadcast
  159.  
  160. typedef struct ConditionWaiter ConditionWaiter;
  161. typedef struct
  162.     {
  163.     MutexLock       *lock;
  164.     ConditionWaiter *head;
  165.     ConditionWaiter **tail;
  166.     } ConditionVar;
  167.  
  168. extern void ConditionVarInit(ConditionVar *c, MutexLock *lock);
  169. extern void ConditionVarWait(ConditionVar *c);
  170. extern void ConditionVarSignal(ConditionVar *c);
  171. extern void ConditionVarBroadcast(ConditionVar *c);
  172.  
  173. #endif
  174.